1. Field of the Invention
The present invention relates to methods for determining the placement of elements in layouts of electrical and electronic circuits and, more particularly, to methods for automatically developing layout arrangements for circuits initially represented as netlists generated by compiler systems.
2. State of the Art
Generally speaking, a netlist is a compilation of information that represents the interconnections between instances of electronic parts, such as cells, in electrical or electronic circuits. Netlists are widely used in conjunction with electronic logic circuits where, for example, element definitions, or "instances," may be as simple as a resistor or as complex as a microprocessor. Netlists do not, however, contain information as to how instances are to be placed relative to one another in physical circuits. For example, even though a netlist may list instances "A" and "B" as being interconnected, these two instances may be immediately adjacent one another, or may be separated physically by hundreds, or even thousands, of other instances in a physical realization of the netlist.
Netlists can be generated by circuit design systems known as datapath compilers. In practice, datapath compilers produce netlists from "high level" schematics. Most datapath compilers produce "optimized" layout arrangements. The optimized layouts are useful because they produce datapaths that contain relatively small quantities of wiring.
The term "datapath," as used in the present context, refers to grids of horizontally and vertically directed wires that have digital logic elements located at some of their intersections. For example, the horizontally-directed wires can be databuses for arithmetic logic units. In that case, the vertically-directed wires are normally used for control, shift and carry signals.
The determination of cell placement locations from netlists is normally done by place-and-route, or placement, processes. Placement processes allow a circuit designer to provide physical circuit layouts from netlists. One example of a placement process is disclosed in U.S. Pat. No. 3,617,714 to Kernighan et al. Another example of a placement process is disclosed in an article by C. M. Fiduccia et al., "A Linear-Time Heuristic For Improving Network Partitions", Proceedings of the 19th ACM Design Automation Conference (1982).
The article "MINCUT Placement" by M. A. Breuer in the Journal of Design Automation Fault-Tolerant Computing, Vol. 1, 1977, pp. 343-362, provides an exemplary MINCUT placement process for determining instance locations in layouts when circuit information is initially provided by netlists. According to the MINCUT placement process, all instances of a netlist are initially placed into a rectangular area, and then the area is recursively partitioned both vertically and horizontally. For example, an area that initially contains all of the netlist instances may be first cut horizontally into two areas; then, the area may be cut vertically into four areas, and so forth.
At each step in the MINCUT process, the object is to minimize the number of node connecting signal lines, or "nets" that cross a partitioning line while maintaining balance between the two sections of a partitioned area according to a predetermined criterion. Whenever an instance is moved across a partition line, an evaluation is made to determine the change in the number of nets crossing the partition.
In the evaluation, the "cost" of moving an instance is measured by the number of nets that cross the partition. Only instance moves that do not violate the predetermined criterion are allowed, and each instance is moved once, and ,only once, per pass. The instance move that most improves the cost function (or least degrades the function) is selected as the "best" move. Whenever a balanced partition with a cost better than any previously balanced partition is attained, that partition is deemed to be the optimal partition and is used for evaluating subsequent partitions.
Typically, a MINCUT optimization process is continued, with alternating horizontal and vertical cuts, until each partitioned area contains less than a specified number of instances. Then, in standard cell placement, partitioned instances are formed into rows.
Place-and-route processes such as the MINCUT process are aimed at minimizing the total length of all wires. Although these processes are relatively effective, it would be desirable to further optimize the organization of a circuit layout originally specified as a netlist.